'''
https://leetcode.cn/problems/create-maximum-number/description/
'''
from typing import List


class Solution:

    def compare(self, nums1, nums2, i=0, j=0):
        # 比较两个数组大小，从指定下标开始
        m, n = len(nums1), len(nums2)
        while i < m and j < n:
            if nums1[i] != nums2[j]:
                return nums1[i] - nums2[j]
            i, j = i + 1, j + 1
        return (m - i) - (n - j)

    def merge(self, nums1, nums2, i=0, j=0):
        m, n = len(nums1), len(nums2)
        res = []
        while i < m and j < n:
            if self.compare(nums1, nums2, i, j) > 0:
                res.append(nums1[i])
                i += 1
            else:
                res.append(nums2[j])
                j += 1
        res.extend(nums1[i:] if i < m else nums2[j:])
        return res

    def max_seq(self, nums, k):
        # 在序列中，选择k个元素，能组成的最大序列
        stack = []                  # 单调栈，小压大
        n_discard = len(nums) - k   # 可以丢弃的元素数量
        for num in nums:
            while stack and n_discard and num > stack[-1]:
                stack.pop()
                n_discard -= 1
            stack.append(num)
        return stack[0:k]

    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
        m, n = len(nums1), len(nums2)
        res = [0] * k
        start, end = max(0, k - n), min(k, m)  # 在第一个数组能选择元素的区间，最少0或 k-n个， 最多k或m个
        for n_chose in range(start, end + 1):
            seq1 = self.max_seq(nums1, n_chose)
            seq2 = self.max_seq(nums2, k - n_chose)
            cur = self.merge(seq1, seq2)
            if self.compare(cur, res) > 0:
                res = cur
        return res

nums1 = [2,5,6,4,4,0]
nums2 = [7,3,8,0,6,5,7,6,2]
k = 15
obj = Solution()
# print(obj.max_seq(nums2, 2))
print(obj.maxNumber(nums1, nums2, k))